\documentclass[a4paper,spanish]{article}

\input{preambulo}

\hyphenation{ob-te-ner}

\begin{document}

\input{caratula}

\tableofcontents

\newpage
\section{Introducci'on}


\section{Modificiones a la gramática}

Como la gramática

$$G =< \{E\}, \{caracter, |, *, +, ?, ., (, )\}, P, E >$$

\begin{center}
\begin{tabular}{rcl}
P : E&$\rightarrow$&EE\\
&$|$&E$|$E\\
&$|$&E$*$\\
&$|$&E$+$\\
&$|$&E?\\
&$|$&(E)\\
&$|$&caracter\\
&$|$&.\\
\end{tabular}    
\end{center}

es ambigua, hay que reescribirla para que sea LL(1). Para ver que es ambigua alcanza con ver que podemos generar \emph{abc} asociando a derecha o a izquierda.

La transformamos y la reescribimos de la siguiente manera:

$$G =< \{E, A4, A3, A2, A1, A0\}, \{caracter, |, *, +, ?, ., (, )\}, P, E >$$

\begin{center}
\begin{tabular}{r@{ \ : \ }l}
A0	& `('{} E `)' $|$ CARACTER $|$ DOT\\
A1	& A0 OP*\\
A3	& A1+\\
A4	& A3 (`$|$'{} A3)*\\
E	& A4\\
OP		&	`+' $|$ `?' $|$ `*'\\
CARACTER 	&	`{}a'..`z' $|$ `{}A'..`Z' $|$ `0'..`9' $|$ `\ '\\
DOT	&	`.'\\
\end{tabular}
%~ \begin{verbatim}
%~ a0	: '('e')' | CARACTER | DOT;
%~ a1	: a0 OP*;
%~ a3	: a1+;
%~ a4	: a3 ('|' a3)*;
%~ e	: a4;
%~ OP		:	'+' | '?' | '*';
%~ CARACTER 	:	'a'..'z' | 'A'..'Z' | '0'..'9' | ' ';
%~ DOT	:	'.';    
%~ \end{verbatim}
\end{center}


\section{Implementación de un parser que reconozca expresiones regulares}

Para la implementación del parser utilizamos ANTLR\cite{antlr}. Como código inicial utilizamos:
\begin{verbatim}
regex:	e'\n';
a0:	'('e')' | CARACTER | DOT;
a1: a0 (OP)*; 
a3: (a1)+;
a4:	a3 ('|' a3)*;
e:  a4;

OP:		'+' | '?' | '*';
CARACTER:	'a'..'z' | 'A'..'Z' | '0'..'9' | ' ';
DOT:		'.';
\end{verbatim}

Este código fue modificado para que genere los autómatas no determinísticos que acepten las cadenas
que se corresponden con la expresión y luego son determinizados.

\lstinputlisting[language=Ant, showstringspaces=false, frame=single, tabsize=2, captionpos=b, breaklines=true, basicstyle=\footnotesize, numbers=left, numberstyle=\footnotesize]{../regexs.g}

\pagebreak
\subsection{¿Cómo construimos el autómata?}

Breve seguimiento de c'omo generamos el autómata para la entrada \verb_(a+|b*)?.c*_
 
\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{1-empty-crop.pdf}
\caption{Empezamos con un autómata vacío}
\end{center}
\end{figure}

%~ \begin{figure}[h!]
%~ \begin{center}
%~ \includegraphics[scale=1]{2-empty-crop.pdf}
%~ \caption{Empezamos con u autómata vacío}
%~ \end{center}
%~ \end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{3-char-crop.pdf}
\caption{Un autómata para `a'}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{4-autMas-crop.pdf}
\caption{Construimos `a+'}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{6-concat-crop.pdf}
\caption{Compongo con el vacío original}
\end{center}
\end{figure}

%~ \begin{figure}[h!]
%~ \begin{center}
%~ \includegraphics[scale=1]{7-concat-final-crop.pdf}
%~ \caption{}
%~ \end{center}
%~ \end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{7-empty-crop.pdf}
\caption{Otro vacío más}
\end{center}
\end{figure}
%~ 
\pagebreak

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{8-char-crop.pdf}
\caption{Autómata para `b'}
\end{center}
\end{figure}
%~ 
\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{9-autStar-crop.pdf}
\caption{Construímos `b*'}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{11-concat-crop.pdf}
\caption{Concatenamos con el vacío inicial de esta expresión}
\end{center}
\end{figure}

%~ \begin{figure}[h!] %Repetido
%~ \begin{center}
%~ \includegraphics[scale=1]{12-concat-final-crop.pdf}
%~ \caption{}
%~ \end{center}
%~ \end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{12-union-crop.pdf}
\caption{Unión de `a+' y `b*'}
\end{center}
\end{figure}

\pagebreak


\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{13-autOptional-crop.pdf}
\caption{Ahora lo hacemos optativo (es decir, agregamos el `?')}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.78]{15-concat-crop.pdf}
\caption{Lo concatenamos al original vacío}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{16-char-crop.pdf}
\caption{Ahora creamos el que reconoce `.'. A modo ilustrativo tenemos sólo un par de letras y el espacio.}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{17-concat-crop.pdf}
\caption{Agregamos el punto, alcanzando `(a+$|$b*)?.' }
\end{center}
\end{figure}

\pagebreak

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=1]{18-char-crop.pdf}
\caption{Autómata para `c'}
\end{center}
\end{figure}

\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{19-autStar-crop.pdf}
\caption{Autómata para `c*'}
\end{center}
\end{figure}



\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.8]{21-concat-crop.pdf}
\caption{Concatenamos todo}
\end{center}
\end{figure}

%~ \begin{figure}[h!] % repetido
%~ \begin{center}
%~ \includegraphics[scale=0.8]{22-concat-final-crop.pdf}
%~ \caption{}
%~ \end{center}
%~ \end{figure}




\begin{figure}[h!]
\begin{center}
\includegraphics[scale=0.93]{00-final-crop.pdf}
\caption{Autómata final, una vez determinizado}
\end{center}
\end{figure}

\pagebreak

\section{C'omo ejecutar el TP}

El TP funciona con las versiones 2.4, 2.5, 2.6 y 2.7 de Python, al menos.
Suministramos Antlr3 junto con nuestra soluci'on en el directorio \texttt{antlr-3.1.3} para facilitar su ejecuci'on.
Para generar las clases que parsean y tokenizan s'olo es preciso tener instalada alguna versi'on de java, y dichas clases
se pueden generar ejecutando:
\begin{verbatim}
./create_classes.sh regexs.g
\end{verbatim}
en el directorio \texttt{el\_tp}. Esto crea los archivos \texttt{regexsLexer.py} y \texttt{regexsParser.py}, que son los que usa
el TP para tokenizar y luego parsear las expresiones regulares, respectivamente.

Pero para poder ejecutar el TP es necesario instalar el runtime de Antlr para Python.
Para esto, hay que bajar e instalar setuptools, yendo a la p'agina:
\begin{verbatim}
http://pypi.python.org/pypi/setuptools
\end{verbatim}
y bajando el \texttt{.egg} correspondiente a la versi'on de Python. Para instalarlo se tiene que ejecutar ese \texttt{.egg} como si fuera un script de bash:
\begin{verbatim}
sudo sh setuptools-0.6c11-py2.7.egg
\end{verbatim}
Una vez hecho esto se instala el runtime yendo al directorio \texttt{antlr-3.1.3/runtime/Python} y ejecutando:
\begin{verbatim}
sudo python setup.py install
\end{verbatim}

El TP se ejecuta estando en el directorio \texttt{el\_tp} con el comando:
\begin{verbatim}
python eval.py archivo_a_parsear
\end{verbatim}
Luego de ingresar esto se espera que se ingrese la expresi'on regular que se quiere buscar. 'Esta tiene que terminarse con un salto
de l'inea y luego un fin de l'inea (\texttt{CTRL-D}).

\subsection{Tests}
En el directorio \texttt{tests} hay varios archivos para testear el TP. En el archivo \texttt{regexs} hay una lista
de expresiones regulares y el archivo al cual se le aplican.





\appendix
\section{Links}
\begin{thebibliography}{99}
\bibitem{antlr} ANother Tool for Language Recognition (ANTLR)\url{http://www.antlr.org/}  
\end{thebibliography}

\label{fin}

\end{document}

